翻訳と辞書 Words near each other ・ Self-governing colony ・ Self-Government Army ・ Self-Government Guiding Board ・ Self-gravitation ・ Self-guided tour ・ Self-handicapping ・ Self-harm ・ Self-hating Jew ・ Self-assessment ・ Self-assessment (disambiguation) ・ Self-authenticating document ・ Self-authorship ・ Self-averaging ・ Self-avoiding walk ・ Self-awareness ・ Self-balancing binary search tree ・ Self-balancing two-wheeled board ・ Self-balancing unicycle ・ Self-belay ・ Self-bondage ・ Self-brand ・ Self-build ・ Self-cannibalism ・ Self-care deficit nursing theory ・ Self-categorization theory ・ Self-censorship ・ Self-Certification (New York City Department of Buildings) ・ Self-certifying File System ・ Self-certifying key ・ Self-Changing Gears Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Self-balancing binary search tree ： ウィキペディア英語版 Self-balancing binary search tree In computer science, a self-balancing (or height-balanced) binary search tree is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.〔 Donald Knuth. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 6.2.3: Balanced Trees, pp.458–481. 〕 These structures provide efficient implementations for mutable ordered lists, and can be used for other abstract data structures such as associative arrays, priority queues and sets. The Red-black tree, which is a type of self-balancing binary search tree, was called Symmetric binary B-tree 〔 Paul E. Black, "SBB tree", in Dictionary of Algorithms and Data Structures (), Vreda Pieterse and Paul E. Black, eds. 17 December 2004. (accessed 28 September 2015) Available from: http://www.nist.gov/dads/HTML/sbbtree.html 〕 and was renamed but can still be confused with the generic concept of self-balancing binary search tree because of the initials. == Overview == Most operations on a binary search tree (BST) take time directly proportional to the height of the tree, so it is desirable to keep the height small. A binary tree with height ''h'' can contain at most 20+21+···+2''h'' = 2''h''+1−1 nodes. It follows that for a tree with ''n'' nodes and height ''h'': $n\backslash le2^-1$ And that implies: $h\backslash ge\backslash lceil\backslash log\_2(n+1)-1\backslash rceil\backslash ge\; \backslash lfloor\backslash log\_2\; n\backslash rfloor$. In other words, the minimum height of a tree with ''n'' nodes is log2(''n''), rounded down; that is, $\backslash lfloor\; \backslash log\_2\; n\backslash rfloor$.〔 However, the simplest algorithms for BST item insertion may yield a tree with height ''n'' in rather common situations. For example, when the items are inserted in sorted key order, the tree degenerates into a linked list with ''n'' nodes. The difference in performance between the two situations may be enormous: for ''n'' = 1,000,000, for example, the minimum height is $\backslash lfloor\; \backslash log\_2(1,000,000)\; \backslash rfloor\; =\; 19$. If the data items are known ahead of time, the height can be kept small, in the average sense, by adding values in a random order, resulting in a random binary search tree. However, there are many situations (such as online algorithms) where this randomization is not viable. Self-balancing binary trees solve this problem by performing transformations on the tree (such as tree rotations) at key insertion times, in order to keep the height proportional to log2(''n''). Although a certain overhead is involved, it may be justified in the long run by ensuring fast execution of later operations. Maintaining the height always at its minimum value $\backslash lfloor\; \backslash log\_2(n)\; \backslash rfloor$ is not always viable; it can be proven that any insertion algorithm which did so would have an excessive overhead. Therefore, most self-balanced BST algorithms keep the height within a constant factor of this lower bound. In the asymptotic ("Big-O") sense, a self-balancing BST structure containing ''n'' items allows the lookup, insertion, and removal of an item in O(log ''n'') worst-case time, and ordered enumeration of all items in O(''n'') time. For some implementations these are per-operation time bounds, while for others they are amortized bounds over a sequence of operations. These times are asymptotically optimal among all data structures that manipulate the key only through comparisons. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Self-balancing binary search tree」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.